package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 快速升序排序（很重要）
 */
public class p35_快速排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        System.out.println("=========================");
        int[] res = quackSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }

////  快速排序可以在力扣912通过，但是效果不好
//    public static int[] quackSort(int[] nums) {
//        return sort(nums, 0, nums.length-1);
//    }
//    public static int[] sort(int[] array, int start, int end){
//        if(array.length<1||start<0||end>=array.length||start>end)
//            return null;
////        数据分割成独立的两部分时，从哪儿分区的指示器
//        int zoneIndex = partition(array, start, end);
//        if(zoneIndex > start)
//            sort(array, start, zoneIndex-1);
//        if(zoneIndex < end)
//            sort(array, zoneIndex+1, end);
//        return array;
//    }
//    public static int partition(int[] array, int start, int end){
////        只有一个元素时，无序再分区
//        if(start == end) return start;
////        随机选择一个基准数
//        int pivot = (int)(start + Math.random() * (end-start+1));
////        zoneIndex是分区指示器，初始值为分区头元素下标减一
//        int zoneIndex = start - 1;
////        将基准数和分区尾元素交换位置
//        swap(array, pivot, end);
//        for(int i = start; i <= end; i++){
////            当元素小于等于基准数
//            if(array[i] <= array[end]){
////                首先分区指示器累加
//                zoneIndex ++;
////                当前元素在分区指示器的右边时，交换当前元素和分区指示器元素
//                if(i > zoneIndex)
//                    swap(array, i, zoneIndex);
//            }
//        }
//        return zoneIndex;
//    }
//    public static void swap(int[] array, int i, int j){
//        int temp = array[i];
//        array[i] = array[j];
//        array[j] = temp;
//    }

//    自己尝试写
    public static int[] quackSort(int[] nums) {
        return sort(nums, 0, nums.length-1);
    }
    public static int[] sort(int[] array, int start, int end){
        if(array.length<1||start<0||end>=array.length||start>end) return null;
        int zoneIndex = partition(array, start, end);
        if(zoneIndex > start)
            sort(array, start, zoneIndex-1);
        if(zoneIndex < end)
            sort(array, zoneIndex+1, end);
        return array;
    }
    public static int partition(int[] array, int start, int end){
        if(start==end) return start;
        int pivot = (int)(start+Math.random()*(end-start+1));
        int zoneIndex = start-1;
        swap(array, pivot, end);
        for (int i=start; i<=end; i++){
            if(array[i]<=array[end]){
                zoneIndex++;
                if(i>zoneIndex){
                    swap(array, i, zoneIndex);
                }
            }
        }
        return zoneIndex;
    }
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
